package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/13.
 */
public class Permutations {
    private LinkedList<Integer> tmp = new LinkedList<Integer>();
    private List<List<Integer>> rst = new LinkedList<List<Integer>>();

    private void perMu(int start, int[] num) {
        if (start == num.length) {
            List<Integer> tmpp = new LinkedList<Integer>();
            for (Integer tm : tmp) {
                tmpp.add(tm);
            }
            rst.add(tmpp);
        } else {
            for (int i = start; i < num.length; i++) {
                int t = num[start];
                num[start] = num[i];
                num[i] = t;
                tmp.add(num[start]);
                perMu(start + 1, num);
                tmp.removeLast();
                t = num[i];
                num[i] = num[start];
                num[start] = t;
            }
        }
    }

    public List<List<Integer>> permute(int[] num) {
        if (num == null || num.length == 0)
            return rst;
        perMu(0, num);
        return rst;
    }

    public static void main(String[] args) {
        Permutations permutations = new Permutations();
        int[] num = {1, 2};
        System.out.println(permutations.permute(num));
    }
}
